package src.BlueBridge.DeepRecursion;

/**
 * 有一个X*Y的网格，一个机器人只能走格点且只能向右或者向下走，要从左上角走到右下角
 * 请设计一个算法，计算机器人有多少种走法
 * 给定两个正整数int x, int y，请返回机器人的走法数目，保证x+y小于等于12
 *
 * 顺着想，倒着写
 */

public class _2机器人走格子 {
    public static void main(String[] args) {
        System.out.println(solve(2, 3));
        System.out.println(solve1(3, 3));
    }

    // 神了解递归
    public static int solve(int x, int y) {
        if (x == 1 || y == 1)
            return 1;
        return solve(x - 1, y) + solve(x, y - 1);
    }

    // 人了解迭代
    public static int solve1(int m, int n) {
        int[][] state = new int[m + 1][n + 1];
        for (int i = 1 ; i <= n ; i++) {
            state[1][i] = 1;
        }
        for (int i = 1 ; i <= m ; i++) {
            state[i][1] = 1;
        }
        for (int i = 2 ; i <= m ; i++) {
            for (int j = 2 ; j <= n ; j++) {
                state[i][j] = state[i - 1][j] + state[i][j - 1];
            }
        }
        return state[m][n];
    }

    // 迭代
    public static int mySolve1(int x, int y) {
        int[][] nums = new int[x + 1][y + 1];
        // 初始化
        for (int i = 1 ; i <= x ; i++) {
            nums[1][i] = 1;
        }
        for (int i = 1 ; i <= y ; i++) {
            nums[i][1] = 1;
        }
        for (int i = 2 ; i <= x ; i++) {
            for (int j = 2 ; j <= y ; j++) {
                nums[i][j] = nums[i - 1][j] + nums[i][j - 1];
            }
        }
        return nums[x][y];
    }
}
